package com.lsa.letcode.the78.subsets;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        Arrays.sort(nums);
        
        List<List<Integer>> subsets = new ArrayList<List<Integer>>();
        
        Combination c = new Combination(nums);
        do{
        	subsets.add(new ArrayList<>(c.asList()));
        }
        while(c.next());
        
        return subsets;
    }
    
    static class Combination {
    	int[] bits;
		private int[] ints;
    	
    	Combination(int[] ints) {
    		bits = new int[ints.length];
    		this.ints = ints;
    	}
    	
    	List<Integer> asList(){
    		List<Integer> l = new ArrayList<Integer>();
    		
    		for (int i = 0; i < bits.length; i++) {
				if (bits[i] != 0) {
					l.add(ints[i]);
				}
			}
    		
    		return l;
    	}
    	
    	void flip(int i, int bit) {
    		bits[i] = bit;
    	}
    	
    	boolean next(){
    		if (bits.length == 0) {
    			return false;
    		}
    		int carry = 0;
        	for (int i = bits.length - 1; i > -1; i--) {
    			int d = bits[i] + carry + (i == bits.length - 1? 1 : 0);
    			carry = d / 2;
    			d = d % 2;
    			flip(i, d);
    		}
    		return carry == 0;
    	}
    }
}